
\section{排序算法}

\subsection{排序算法分类}
\label{subsec:sortAthmClass}

根据\cite{acp},排序算法包括内部排序和外部排序(不完全放入RAM)。内部排序分类：插入，交换，选择，合并，分布。
根据\cite{ita},排序算法包括基于比较的排序和非基于比较的排序(可以达到线性时间复杂度)。
\cite{weijipedia}给出了丰富的讲解材料。
\begin{verbatim}
http://en.wikipedia.org/wiki/Sorting_algorithm
\end{verbatim}

\begin{description}
    \item[基于插入的排序] 
        \hfill \\
	\begin{description}
	    \item[直接插入]就地稳定。$O(N^2)$。参\cite{ita}2.2。适用于近似有序数组。快速排序和插入排序可以联合使用，性能极佳。
	    \item[Shell排序]就地，不稳定。\cite{acp}5.2.1D。也称递减增量排序算法，不需要大量的辅助空间，不稳定，复杂度取决于降序序列的选取，可能是$O(Nlg^{2}(N))，O(NlogN), N^{\frac{6}{5}}$。
	    \item[图书馆排序]有n个元素待排序，这些元素被插入到拥有(1+e)n个元素的数组中。
	    \item[(二叉)树排序]稳定。线性空间复杂度。先构造二叉查找树，再in-order遍历之。从文件中读数时比较方便。平均时间$O(NlogN),二叉树不平衡时最差O(N^2)$。
	    \item[其他]二路插入(使用二分法查找合适度位置，但未能减小移动数据度开销)，表插入(以链表实现，减小数据复制开销)，地址计算插入等。
	\end{description}
    \item[基于交换的排序] 
        \hfill \\
	\begin{description}
	    \item[冒泡]稳定就地排序。$O(N^2)$。数据交换过多，\cite{acp}认为不值得推荐。
	    \item[鸡尾酒排序]稳定就地排序。冒泡排序的变种。别名：双向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序，涟漪排序, 来回排序。
	    \item[快速排序]就地不稳定。平价时间$O(Nlog(N))$，空间$O(logN)$。\cite{sedgewick}认为快速排序是最快的。
	    \item[奇偶排序]奇偶换位排序，或砖排序。最初发明用于有本地互连的并行计算。
	    \item[Gnome Sort]又称stupid sort。类似插入排序，但通过同前面元素交换实现插入。
	    \item[梳子排序]冒泡排序的变种。不稳定。如同快速排序和合并排序，梳排序的效率在开始时最佳，接近结束时，即进入泡沫排序时最差。如果间距变得太小时(例如小于10)，改用诸如插入排序或鸡尾酒排序等算法，则可提升整体效能。
	    \item[其他]合并交换(在可并行比较计算时有用)，基数交换，地址计算插入等。
	\end{description}
    \item[基于选择的排序]
        \hfill \\
	\begin{description}
	    \item[直接选择]就地不稳定。$O(N^2)$。
	    \item[堆排序]就地不稳定。时间$O(Nlog(N))$，空间$O(1)$。\cite{ita}认为堆排序不如快速排序，但有其他用途，如实现优先级队列。	
	    \item[锦标赛排序]基于堆，待排数据初存于叶子节点，决出胜者，将胜者从其上升路径中删除，在存放胜者的叶子节点放置一个大数。时间$O(Nlog(N))$，需要额外空间作为堆。主要用于外排序的多路合并步骤。？

	\end{description}
    \item[基于合并的排序] 
        \hfill \\
	\textbf{归并排序}，非就地，稳定。\cite{ita}2.3节Merge例程先将待合并数组的两个有序子数组拷贝到外部，再拷回原数组使有序。
	比较操作的次数介于$(nlogn)/2$和$nlogn-n+1$，赋值操作的次数是$2nlogn$，空间复杂度为：Θ (n)\cite{weijipedia}。
	\cite{acp}提出了如下两个非递归的归并排序算法，额外分配了与原数组等长的缓冲区。
	\begin{description}
	    \item[自然的两路合并]\cite{acp}5.2.4算法N。
	    \item[直接两路合并]\cite{acp}5.2.4算法S。
	\end{description}
	另外，还有就地不稳定版本的合并排序(\cite{acp}Vol3 习题5.2.5，$O(NlgN)$时间,流程复杂)。也有就地稳定版本(\cite{acp}Vol3习题)的合并排序，流程简单，时间复杂度有所增加,失去了意义。对于就地不稳定版本，分为分块、预排序、两两并归、扫尾四部。分为m+2块，除最后一块外，其他快大小都是$sqrt(n)$。块内排序。块排序，依据块的首元素，如首元素相同则依据末尾元素。然后执行多次AUX排序。\url{http://blog.ibread.net/345/in-place-merge-sort/}.
    \item[基于分布的排序] \hfill \\

	\begin{description}
	    \item[桶排序]\cite{ita}8.4。稳定？，最差时间$O(n+k)$，平均时间$O(n+k)$，需要额外空间存放桶。It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. 
	    \item[鸽巢排序]鸽巢排序(Pigeonhole sort), 也被称作基数分类\cite{weijipedia}(count sort\cite{wikipedia}), 时空复杂度均$O(n+k)$，适用于$k=O(n)$情形，否则不如桶排序。计数排序中元素移动一次，鸽巢排序则移动两次(入、出鸽巢)\cite{wikipedia}.
	    \item[比较计数]\cite{acp}5.2算法C，统计比该记录小的记录的个数。时间$O(N^2)$，空间$O(N)$。无大用。
	    \item[分布计数]\cite{acp}5.2算法D。\cite{ita}8.2。稳定排序。时间$O(n+k)a$，空间$O(k+n)$，k为分布空间大小，需要额外空间存放辅助表和排序结果。若$k=O(n)$,则时空均为$O(n)$。涉及的操作包括prefix sum(cumulative sum).
	    \item[基数排序]\cite{ita}8.3。若每个基数位使用计数排序，则时间$O(d(n+k))$，d为位数，k为基数。
	\end{description}
\end{description}

另外，bogosort（猴子排序）通过随机洗牌来排序，时间复杂度无上限，仅供了解。一个笑话说：量子计算机能够以 O(n) 的复杂度更有效地实现Bogo排序。


\subsection{空间复杂度}
总之，如果不是就地排序，则至少需要$O(N)$的额外空间，如归并排序。快速排序为就地排序，但需要$O(logN)$的空间。
归并排序的主要缺点，是在最佳情况下需要Ω(n)额外的空间\cite{weijipedia}。

\subsection{稳定性}
\cite{weijipedia}
1.稳定的排序
\begin{enumerate}
	\item 冒泡排序, 鸡尾酒排序
	\item 插入排序
	\item 归并排序
	\item 二叉树排序
	\item 鸽巢排序
	\item 桶排序
	\item 计数排序
	\item 基数排序
	\item Gnome sort
	\item 图书馆排序
	\end{enumerate}

	2.不稳定的排序

	\begin{enumerate}
	\item 选择排序
	\item 希尔排序
	\item Comb sort
	\item 组合排序
	\item 堆排序
	\item Smoothsort
	\item 快速排序
	\item Introsort
	\item Patience sort
    \end{enumerate}

\cite{sedgewick}习题2.5.18提出了强制稳定性概念，比如用额外的字段记录每个数据的位置，在不稳定排序操作之后用此字段恢复原来的相对次序。
原地分区版本的快速排序算法是不稳定的。其他变种是可以通过牺牲性能和空间来维护稳定性的\cite{weijipedia}。

\subsection{快速排序}
\label{summary:quicksort}

有许多版本，包括就地非稳定版本和稳定非就地版本。
网上有一些非权威程序员给出了非递归版本，自行实现栈结构以模拟递归调用行为。

\cite{pp}和\cite{sedgewick}提出了以下几种划分方案:
\begin{itemize}
    \item 
	Lomuto划分, x[l]存放t，[l+1,m]小于t,(m,i)大于等于t，[i,u]未知。
    \item 
	双向划分， x[l]存放t，[l+1,m]小于等于t, (m,i)未知，[i,u]大于等于t。
    \item 
	三路划分(\cite{pp}11.5.11称为宽支点划分)。[l, lt)部分小于t，[lt,i)等于t，[i,gt]未知，(gt,u]大于t。
\end{itemize}


对快速排序pivot的选择，早期常使用最左元素，导致对有序数组性能很差。R.Sedgewick提出\cite{wikipedia}选择pivot的方案:
\begin{itemize}
    \item 随机元素
    \item 中间元素
    \item 最左、最右和中间元素的均值
\end{itemize}

他同时提出了两种优化:
\begin{itemize}
    \item 先递归较短的那半数组，以保证最多使用$O(logN)$空间。较长的那半数组使用尾部递归或遍历，可能不额外增加堆栈空间。
    \item 数组段较短时不再排序，最终使用插入排序扫一遍，插入排序对于近似排好的数组很高效。
\end{itemize}

代码示例参考\ref{codes:quicksort}。

内省(introsort)排序集成了快速排序和堆排序。

\subsection{堆排序}

C++标准库提供来堆操作，包括make\_heap, push\_heap, pop\_heap,sort\_heap等。可以用两行代码实现堆排序:
\begin{lstlisting}[language=Python]
    make_heap(a, a+n)
    sort_heap(a, a+n)
\end{lstlisting}

C++标准库也提供了对优先级队列priority\_queue的支持。

基于\cite{pp}14.2给出的两个关键函数siftup和siftdown，仅用几行程序就可实现堆排序。
\begin{lstlisting}[language=Python]
    #make heap
    for i in range(2, len(x)):
	siftup(x, i) #必须是大顶堆
    
    #sort heap
    for i in range(len(x)-1, 1, -1):
	tmp = x[1]; x[1] = x[i]; x[i] = tmp
	siftdown(x, i-1)
\end{lstlisting}
对\cite{pp}14.2节siftup的优化包括x[0]置哨兵，放置一个大数；x[i]上浮时，不交换i,p两个位置，即将swap展开，只置i，不置p。siftdown很难使用哨兵，但也可以通过展开swap来进行优化。


\subsection{外部排序}
主要算法\cite{wikipedia}:
\begin{itemize}
    \item 
        \textbf{外部合并排序}\cite{wikipedia}.涉及的数量概念是pass(取决于算法设计，不宜过多)和way(取决与数据量与RAM空间比值)。pass是步骤数，pass1将子文件排序并存放于way路临时文件，pass2进行多路合并。如果way过多，pass2会因磁盘寻道频繁而效率低下。此时可增加pass数，pass2合并way路为更少的路数，pass3将现有路数合并成1路。
    \item 
	\textbf{外部桶排序}，基于分布的排序。桶排序和合并排序具有数学上的对偶性\cite{weijipedia}。k趟算法可以在kn的时间开销和\verb|n/k|空间开销内完成对最多n个小于n的无重复正整数的排序(选自\cite{pp}1.5答案，每趟使用位图法进行排序)。
\end{itemize}
\cite{pp}1.3的归并排序、多趟排序分别指这里的外部合并排序和外部桶排序。

此外，还有一些不需要临时文件的原地算法。 Merge sort is used in external sorting; heapsort is not. Locality of reference is the issue.



\subsection{整数排序}
\cite{wikipedia}
题目中研究的对象如果是整数，可以在其值域做文章。计算机中的整数取值空间有限且可数。
主要算法:
\begin{itemize}
    \item 
van Emde Boas tree,\cite{ita}第3版第20章，\cite{wikipedia}。
    \item 
non-conservative "packed sorting" algorithm
    \item 
	位图排序，要求key可表示为整数且互异。bit在bit序列中的位置代表整数的值，而bit的值代表存在性。如果整数出现多次\cite{pp}1.6.6，或者需要统计其他属性(而不仅仅是存在性)，可以考虑用多个bit位表示每个整数，bit值代表该属性。如\cite{pp}1.6.8，美国免费电话号(800.887.888)存储问题，可以用3个bit分别表示以800,887,888前缀的特定7位号码是否已经存在\cite{self}。
    \item 
Bucket sort, counting sort, radix sort
\end{itemize}

下面是对位向量的实现\cite{pp}1.6.2:
\begin{verbatim}
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }
\end{verbatim}

Bucket sort, counting sort, radix sort, and van Emde Boas tree sorting all work best when the key size is small; for large enough keys, they become slower than comparison sorting algorithms. 




